The problem can be found at the following link: Question Link
Honestly, if you're not familiar with dynamic programming, I strongly recommend checking out Striver's tutorials for learning DP. He's has provided the well explaining solution for this problem. Just click here to take a look at it.
For now, I solve this knapsack problem with duplicate items using dynamic programming. Here's my approach:
- Create a vector
dp
of sizeW+1
and initialize all elements to 0.dp[i]
will store the maximum value that can be obtained with a knapsack of capacityi
. - Iterate through each item from
0
toN-1
, whereN
is the number of items. - For each item, iterate through the weights from
wt[i]
toW
, whereW
is the maximum knapsack capacity. - Update
dp[w]
by taking the maximum of its current valuedp[w]
and the value of the current item plus the value obtained by using the remaining capacityw - wt[i]
. - Finally, return
dp[W]
, which will contain the maximum value that can be obtained with the given items and their weights.
- Time Complexity:
O(N * W)
, whereN
is the number of items andW
is the maximum knapsack capacity. - Auxiliary Space Complexity:
O(W)
, whereW
is the maximum knapsack capacity.
class Solution {
public:
int knapSack(int N, int W, int val[], int wt[]) {
vector<int> dp(W + 1, 0);
for (int i = 0; i < N; i++) {
for (int w = wt[i]; w <= W; w++) {
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
}
}
return dp[W];
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.